# 分治思想
# 找一个基准，将小的放其左边，大的放其右边
# 直到左右区间 = 1
from typing import List


def quick_sort(target: List[int], left, right):
    if len(target) <= 1 or left >= right:
        return

    l = left
    r = right
    key = target[l]

    while l != r:
        while l < r and key <= target[r]:
            r -= 1
        while l < r and key >= target[l]:
            l += 1
        swap(target, l, r)
    swap(target, left, l)
    quick_sort(target, left, l - 1)
    quick_sort(target, l + 1, right)


def swap(target, a, b):
    temp = target[a]
    target[a] = target[b]
    target[b] = temp


if __name__ == '__main__':
    arr = [3, 421, 3, 111, 6, 123, 2, 4, 5]
    quick_sort(arr, 0, len(arr) - 1)
    print(arr)
